package main

import (
	"fmt"
)



func main()  {
	// len: 12
    head :=[][]int{{4,3,11,5,7,8,10,2,1,6},{2,9,3,11,10,6,7,4,5},
	{10,7,9,4,3,6,11,5},{9,4,11,6,8,10,7,5},{5,7,6,9,8,11,10},{8,7,11,9,10,6},
	{10,7,11,9,8},{9,10,11,8},{10,9},{11,10},{11},{}}
    fmt.Printf("the lend:%d\n",len(head))
	visited :=make([]bool,len(head))
	path:=make([]int,0)
	// path需要传回来
	a_dfs(8,visited,head,&path)
	fmt.Printf("the len: %d,value : %v\n",len(path),path)
	path2,floor:=a_bfs(9,12,head)
	fmt.Printf("the length is : %d , %v \n",len(path2),path2)
	fmt.Printf("the length is : %d , %v \n",len(floor),floor)
}

func a_dfs(cur int,visited []bool, head [][]int, path *[]int) {
	if !visited[cur] {
       visited[cur] = true
       *path =append(*path,cur)
   }
	for _, val:=range head[cur]{
		if !visited[val]{
			// 后面的两个值没有变，是为了变量访问
			a_dfs(val,visited,head,path)
		}
	}
}

// bfs没有使用递归, 变量len会覆盖内置函数len
func a_bfs(start int,l int,head [][]int) ([]int,[]int) {
	visited:=make([]int,l)
	for idx:=range visited{
		visited[idx] = -1
	}
	path :=make([]int,0)
	path =append(path,start)

	q :=make([]int,0)
	q = append(q,start)
    for len(q) >0 {
		st:=q[0]
		q = q[1:]
		// go中和python中都有的range
		for _,val:=range head[st]{
			// 取非和不取非
			if visited[val] ==-1{
				visited[val] = visited[st] +1
				// 说明这个val没有入过队
				path = append(path,val)
				q= append(q,val)
			}
		}
	}
	return path,visited
}